package array

type TopVotedCandidate struct {
	tops  []int
	times []int
}

func Constructor(persons []int, times []int) TopVotedCandidate {
	tops := []int{}
	top := persons[0]
	voteMap := make(map[int]int)

	for _, v := range persons {
		voteMap[v]++
		if voteMap[v] >= voteMap[top] {
			top = v
		}
		tops = append(tops, top)
	}

	return TopVotedCandidate{
		tops:  tops,
		times: times,
	}

}

func (this *TopVotedCandidate) Q(t int) int {

	var mid int
	left := 0
	right := len(this.times) - 1

	for left < right {
		mid = (left + right) / 2

		if t < this.times[mid] {
			right = mid - 1
		} else if t > this.times[mid] {
			left = mid + 1
		} else {
			return this.tops[mid]
		}
	}

	if t < this.times[left] {
		return this.tops[left-1]
	} else if t > this.times[right] {
		return this.tops[left]
	}

	return this.tops[left]

}
